package com.javase.algorithm.datastructure.stringsandarrays;

import com.javase.algorithm.utils.Utils;
import org.springframework.util.comparator.Comparators;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;

/**
 * 合并区间
 *
 * @author liyanhao
 * @create 2022-06-29 19:45
 * https://leetcode.cn/leetbook/read/array-and-string/c5tv3/
 */
public class Merge {
    public static void main(String[] args) {
        int[][] intervals = {{1, 3}, {2, 6,}, {8, 10}, {15, 18}};
        int[][] merge = new Merge().merge2(intervals);
        Utils.printMatrix(merge);
    }

    public int[][] merge(int[][] intervals) {
        if (intervals.length == 0) {
            return new int[0][2];
        }
        //把矩阵中的数组按照第一个元素进行排序
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });
        ArrayList<int[]> merged = new ArrayList<>();
        //遍历添加矩阵中的每个数组
        for (int i = 0; i < intervals.length; i++) {
            int L = intervals[i][0], R = intervals[i][1];
            if (merged.size() == 0 || merged.get(merged.size() - 1)[1] < L) {
                merged.add(new int[]{L, R});
            } else {
                merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], R);
            }
        }
        return merged.toArray(new int[merged.size()][]);
    }

    public int[][] merge2(int[][] intervals) {
        if (intervals.length == 0) {
            return new int[0][2];
        }
        //把矩阵中的数组按照第一个元素从大到小进行排序
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });
        //遍历矩阵，把元素添加到集合中，
        //因为矩阵已经按照数组首个元素进行排序过，
        // 后边只判断第二个元素的大小，来判断是否需要合并或者直接添加
        ArrayList<int[]> merged = new ArrayList<>();
        for (int i = 0; i < intervals.length; i++) {
            int L = intervals[i][0], R = intervals[i][1];
            if (merged.size() == 0 || merged.get(merged.size() - 1)[1] < L) {
                merged.add(new int[]{L, R});
            } else {
                merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], R);
            }
        }

        return merged.toArray(new int[merged.size()][]);

    }
}
